1 Contenido de la clase
Repaso: el problema del intervalo más pesado [01:04-01:14]
La clase retoma el problema que quedó pendiente de la clase anterior: hay una lista de intervalos con su peso y se quiere saber cuál es el intervalo más pesado, es decir, el que acumula mayor peso [01:04-01:14]. El profesor aclara un malentendido frecuente: no se busca el valor máximo de un solo elemento, sino la suma de los pesos del intervalo [03:54-03:58].
La tabla de programación dinámica [04:00-05:33]
Sobre un ejemplo con muchos valores [02:52-03:38], el profesor comienza a construir la tabla de programación dinámica: para cada posición se mira el intervalo anterior compatible, se comparan las dos opciones (tomar el intervalo y sumar su peso, o dejarlo de lado) y se guarda el mejor valor; en un punto del ejemplo se comparan los candidatos 6 y 8 [04:20-04:35]. La idea clave es que la respuesta de cada subproblema se obtiene en tiempo constante usando los valores ya calculados [05:31-05:33]. [parte no entendida: los números concretos de la tabla se pierden por el ruido de la grabación]
Definir la operación básica [06:49-07:07]
El profesor plantea que, para hablar de complejidad, primero hay que definir qué es una operación básica en un programa [06:49-06:56]. La operación básica que se va a estudiar es la comparación entre dos elementos [07:07], y anuncia que verán los esquemas básicos de diseño de algoritmos [07:11]. [parte no entendida: desarrollo de esta parte]
La pregunta: ¿cuántas comparaciones cuesta ordenar? [09:00-20:10]
Se plantea la pregunta central: dados 3, 4 o n números desordenados, ¿cuál es la complejidad de ordenarlos? [09:00-09:10]. Se supone que los números son los enteros de 1 a n, todos distintos, es decir, una permutación [20:06-20:10]. El profesor recuerda que "ya se ha oído" que se puede ordenar en O(n log n) y pregunta si se puede hacer mejor.
El árbol de decisiones (árbol de comparaciones) [23:29-23:31]
Todo algoritmo de ordenamiento que solo usa comparaciones se puede modelar como un árbol de decisiones: cada nodo interno es una comparación entre dos elementos y cada hoja es un resultado posible (una permutación) [23:29-23:31]. Como hay n! permutaciones distintas, el árbol tiene que tener al menos n! hojas [40:17-40:41].
El límite inferior Ω(n log n) [40:48-47:52]
Un árbol binario de altura h tiene como máximo 2^h hojas. Para que quepan las n! hojas se necesita 2^h ≥ n!, de donde la altura debe cumplir:
h ≥ log₂(n!) = Θ(n log n)
Como la altura del árbol es el número de comparaciones en el peor caso, cualquier algoritmo de ordenamiento por comparaciones necesita al menos Ω(n log n) comparaciones [46:55-47:52, 65:05]. Aplicado a casos concretos: para ordenar 4 números, log₂(4!) = log₂(24) ≈ 4.5, así que hacen falta al menos 5 comparaciones [40:00-40:02]; para 3 números, log₂(6) ≈ 2.5, al menos 3 [40:08]. "Esta sería la complejidad de ordenar 4 números" [64:44-64:48].
Construyendo el árbol a mano [61:04-80:14]
El profesor construye árboles de comparación con elementos etiquetados (A, B, C, D, F), mostrando cómo cada comparación —"c es menor que d", "a es menor que d", "a con b"— [61:16-61:27, 80:00-80:14] ramifica el árbol y cómo al final cada hoja deja el orden determinado. Insiste en que, sea cual sea el algoritmo "favorito" que se elija [46:44-46:51], el número de comparaciones en el peor caso no puede bajar de log₂(n!). La clase cierra anunciando que el tema continúa la próxima clase [81:55-81:59].
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se indicaron tareas ni fechas de entrega. El profesor cerró diciendo que el tema continúa en la clase siguiente [81:55-81:59]. Conviene repasar:
[parte no entendida — algunos ejemplos numéricos de la pizarra]
4 Dudas que podrían examinar
¿Por qué el árbol de decisiones debe tener al menos n! hojas?
Porque hay n! permutaciones posibles y cada hoja representa un resultado (un orden) distinto; el algoritmo debe poder producir todos [40:17-40:41].
¿De dónde sale el límite inferior?
De 2^h ≥ n!: un árbol de altura h tiene a lo sumo 2^h hojas, así que h ≥ log₂(n!); como log₂(n!) es Θ(n log n), se necesitan Ω(n log n) comparaciones en el peor caso [46:55-47:52].
¿Qué es la altura del árbol de decisiones?
La longitud del camino más largo de la raíz a una hoja; equivale al número de comparaciones en el peor caso [46:55-47:06].
¿Cuántas comparaciones mínimas se necesitan para ordenar 4 números?
Al menos 5, porque log₂(4!) = log₂(24) ≈ 4.58 y el número de comparaciones debe ser entero [40:00-40:02].
¿Este límite vale para cualquier algoritmo de ordenamiento?
Solo para los que ordenan por comparaciones; técnicas que aprovechan otras propiedades de los datos (como el ordenamiento por conteo) pueden ser más rápidas.
¿Por qué en el problema de intervalos se habla de "sumar los pesos"?
Porque se busca el intervalo de mayor peso acumulado, no el máximo de un solo elemento; se comparan opciones como tomar el intervalo (sumando su peso al valor anterior compatible) o dejarlo de lado [03:54-04:35].
5 Sitios o recursos para visitar
El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:
Demostración estándar con árboles de decisión: n! hojas y h ≥ log₂(n!). · google.com
Libro de referencia clásico; incluye el límite inferior del ordenamiento por comparaciones. · google.com
Capítulo 6: weighted interval scheduling y su programación dinámica con p(j). · google.com
Explicación con ejemplos de la programación dinámica OPT(j) = max(v_j + OPT(p(j)), OPT(j−1)). · geeksforgeeks.org
6 Glosario de términos
- Intervalo más pesado: el intervalo de una lista que acumula el mayor peso (mayor suma de sus pesos); no es el valor máximo de un solo elemento.
- Programación dinámica: técnica que resuelve un problema guardando las soluciones de subproblemas; en el ejemplo, cada subproblema se responde en tiempo constante usando valores ya calculados.
- Operación básica: la unidad de trabajo que se cuenta para medir la complejidad de un algoritmo; en esta clase, la comparación entre elementos.
- Permutación: uno de los n! ordenamientos posibles de n elementos distintos.
- Árbol de decisiones (árbol de comparaciones): modelo de un algoritmo de ordenamiento por comparaciones; cada nodo interno es una comparación y cada hoja es un resultado posible.
- Hoja: extremo del árbol donde queda determinado el resultado (un orden de los elementos).
- Altura del árbol: el camino más largo de la raíz a una hoja; equivale al número de comparaciones en el peor caso.
- Factorial n!: n · (n−1) · … · 1; el número de permutaciones de n elementos.
- log₂(n!): logaritmo en base 2 del factorial; es Θ(n log n) y marca el número mínimo de comparaciones para ordenar.
- Límite inferior: cantidad mínima de operaciones (comparaciones) que cualquier algoritmo del modelo debe hacer en el peor caso.
- Ω(n log n): notación que indica que el costo crece al menos como n log n (el límite inferior del ordenamiento por comparaciones).
- Ordenamiento por comparaciones: algoritmo que solo usa comparaciones entre pares de elementos para decidir el orden (por ejemplo, los esquemas clásicos de la asignatura).
7 Mapa mental textual
- Diseño y Análisis de Algoritmos · Clase 2
- Repaso del problema de intervalos (clase anterior)
- Hallar el intervalo de mayor peso → se suman los pesos (no el máximo de un solo valor)
- Tabla de programación dinámica: comparar tomar / no tomar → respuesta en tiempo constante
- Operación básica
- La comparación entre elementos → base para medir la complejidad
- Límite inferior del ordenamiento por comparaciones
- Ordenar n números distintos = decidir cuál de las n! permutaciones es la correcta
- Modelo: árbol de decisiones (nodos = comparaciones, hojas = permutaciones)
- El árbol debe tener al menos n! hojas
- Altura h con a lo sumo 2^h hojas → 2^h ≥ n! → h ≥ log₂(n!) = Θ(n log n)
- Conclusión: ordenar por comparaciones cuesta Ω(n log n) en el peor caso
- Ejemplos: 4 números → al menos 5 comparaciones (≈4.5); 3 números → al menos 3 (≈2.5)
- Construcción a mano: árboles con elementos A, B, C, D, F (comparar a con b, c menor que d, etc.)
- Cierre: el tema continúa la próxima clase [81:55-81:59]
- Repaso del problema de intervalos (clase anterior)